package com.yanceysong.codetop.s11_s20;

/**
 * @ClassName S18_Easy_121_买卖股票的最佳时机
 * @Description
 * @date 2025/8/17 22:50
 * @Author yanceysong
 * @Version 1.0
 */
public class S18_Easy_121_买卖股票的最佳时机 {
    /**
     * LeetCode链接
     * <a href="https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/">...</a>
     * <p>
     * 给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
     * 你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
     * 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
     * <p>
     * ==================== 买卖股票的最佳时机算法图解 ====================
     * <p>
     * 算法思路：一次遍历 (One Pass)
     * 1. 维护两个变量 ：
     * .   - `minCost`: 记录到目前为止遇到的最低股价（最低买入成本）。
     * .   - `maxProfit`: 记录到目前为止可以获得的最大利润。
     * 2. 遍历价格数组 ：遍历 `prices` 数组，对于每一天的价格 `price`：
     * .   - 更新最低成本 ：用当前的 `price` 和 `minCost` 比较，更新 `minCost` 为两者中的较小值。这代表我们总是在历史最低点买入。
     * .   - 更新最大利润 ：计算如果今天卖出能获得的利润 (`price - minCost`)，然后用它和 `maxProfit` 比较，更新 `maxProfit` 为两者中的较大值。
     * 3. 返回结果 ：遍历结束后，`maxProfit` 就是所求的最大利润。
     * <p>
     * 执行示例：prices = [7, 1, 5, 3, 6, 4]
     * <p>
     * | price | minCost (更新前) | minCost (更新后) | price - minCost | maxProfit (更新前) | maxProfit (更新后) |
     * |-------|------------------|------------------|-----------------|--------------------|--------------------|
     * |   7   |      MAX_VALUE   |        7         |      7 - 7 = 0      |          0         |          0         |
     * |   1   |        7         |        1         |      1 - 1 = 0      |          0         |          0         |
     * |   5   |        1         |        1         |      5 - 1 = 4      |          0         |          4         |
     * |   3   |        1         |        1         |      3 - 1 = 2      |          4         |          4         |
     * |   6   |        1         |        1         |      6 - 1 = 5      |          4         |          5         |
     * |   4   |        1         |        1         |      4 - 1 = 3      |          5         |          5         |
     * <p>
     * 最终结果：`maxProfit = 5`
     * <p>
     * 时间复杂度：O(n)，我们只需要遍历一次数组。
     * 空间复杂度：O(1)，我们只使用了两个额外的变量。
     * <p>
     * =====================================================================
     */
    public int maxProfit(int[] prices) {
        // 初始化最低成本为整数最大值，确保第一个价格能成为最低成本
        int minCost = Integer.MAX_VALUE;
        // 初始化最大利润为0，因为利润不能是负数
        int maxProfit = 0;

        // 遍历每一天的价格
        for (int currentPrice : prices) {
            // 更新历史最低成本
            minCost = Math.min(minCost, currentPrice);
            // 计算如果今天卖出能获得的利润，并更新最大利润
            maxProfit = Math.max(maxProfit, currentPrice - minCost);
        }

        return maxProfit;
    }

    public static void main(String[] args) {
        S18_Easy_121_买卖股票的最佳时机 solution = new S18_Easy_121_买卖股票的最佳时机();

        System.out.println("=== 买卖股票的最佳时机测试开始 ===");

        // 测试1: 基本功能测试 - 题目示例
        System.out.println("\n--- 测试1: 基本功能测试 (题目示例) ---");
        testBasicExamples(solution);

        // 测试2: 边界情况测试
        System.out.println("\n--- 测试2: 边界情况测试 ---");
        testBoundaryCases(solution);

        // 测试3: 特殊情况测试
        System.out.println("\n--- 测试3: 特殊情况测试 ---");
        testSpecialCases(solution);

        System.out.println("\n=== 所有测试完成 ===");
    }

    /**
     * 测试基本功能 - 题目给出的示例
     */
    private static void testBasicExamples(S18_Easy_121_买卖股票的最佳时机 solution) {
        // 示例1: [7,1,5,3,6,4] -> 5
        int[] prices1 = {7, 1, 5, 3, 6, 4};
        testMaxProfit(solution, prices1, 5, "题目示例1");

        // 示例2: [7,6,4,3,1] -> 0
        int[] prices2 = {7, 6, 4, 3, 1};
        testMaxProfit(solution, prices2, 0, "题目示例2(无利润)");
    }

    /**
     * 测试边界情况
     */
    private static void testBoundaryCases(S18_Easy_121_买卖股票的最佳时机 solution) {
        // 测试1: 空数组
        int[] prices1 = {};
        testMaxProfit(solution, prices1, 0, "空数组");

        // 测试2: 单个元素
        int[] prices2 = {10};
        testMaxProfit(solution, prices2, 0, "单个元素");

        // 测试3: 两个元素，有利润
        int[] prices3 = {1, 5};
        testMaxProfit(solution, prices3, 4, "两个元素，有利润");

        // 测试4: 两个元素，无利润
        int[] prices4 = {5, 1};
        testMaxProfit(solution, prices4, 0, "两个元素，无利润");
    }

    /**
     * 测试特殊情况
     */
    private static void testSpecialCases(S18_Easy_121_买卖股票的最佳时机 solution) {
        // 测试1: 价格单调递增
        int[] prices1 = {1, 2, 3, 4, 5};
        testMaxProfit(solution, prices1, 4, "价格单调递增");

        // 测试2: 价格单调递减
        int[] prices2 = {5, 4, 3, 2, 1};
        testMaxProfit(solution, prices2, 0, "价格单调递减");

        // 测试3: 价格不变
        int[] prices3 = {5, 5, 5, 5, 5};
        testMaxProfit(solution, prices3, 0, "价格不变");

        // 测试4: 价格波动
        int[] prices4 = {3, 3, 5, 0, 0, 3, 1, 4};
        testMaxProfit(solution, prices4, 4, "价格波动");

        // 测试5: 最低点在最后一天
        int[] prices5 = {10, 20, 30, 1};
        testMaxProfit(solution, prices5, 20, "最低点在最后一天");

        // 测试6: 最高点在第一天
        int[] prices6 = {30, 1, 2, 3};
        testMaxProfit(solution, prices6, 2, "最高点在第一天");
    }

    /**
     * 测试最大利润的辅助方法
     */
    private static void testMaxProfit(S18_Easy_121_买卖股票的最佳时机 solution, int[] prices, int expected, String description) {
        int actual = solution.maxProfit(prices);
        System.out.print(description + " - 输入: " + java.util.Arrays.toString(prices));
        System.out.print(" -> 输出: " + actual);
        System.out.println(" (期望: " + expected + ")");
        assert actual == expected : description + " 测试失败";
    }
}

